1. Field of the Invention
The present invention concerns computer-memory allocators and in particular mechanisms that they employ for coalescing memory blocks.
2. Background Information
Some of the instructions that a processor reads from its memory direct it to read data stored in other memory locations. The program as loaded often specifies the locations in which the data are to be stored: memory is allocated statically. But many programs generate large quantities of intermediate results that require only temporary storage. To use memory efficiently, memory should not be allocated to such results unless and until they are actually produced: it should be allocated dynamically. And, once the program no longer needs the data for which space was thus allocated, the program should be allowed to reuse that memory space.
For this reason, most large programs employ a “heap” of dynamically allocable memory. As the program proceeds, various previously free memory blocks within the heap contain needed data, while other memory blocks become free for reuse because they contain data that are no longer needed. To keep track, the computer system usually maintains an inventory of the locations and sizes of “free” memory blocks, i.e., of memory blocks that can receive new results.
Now, computer programs typically deal with data as various-sized “objects,” each of which typically has all of its data stored in contiguous memory locations. So a block of (contiguous) memory locations must be found when the time comes to allocate memory dynamically to an object. An allocator is the system component that handles the task of keeping track of such free memory blocks and determining which of the free memory blocks are to be used to store new data.
Allocators occur at various levels in the software hierarchy. An operating system itself generates data for which it must dynamically allocate memory, so one of an operating system's tasks is to act as an allocator for that purpose. The operating system typically also serves as an allocator in response to various system calls made by applications programs. The C library function malloc( ), for instance, is a system call that an application uses to ask the system to allocate memory to the application. The free( ) library function conversely tells the system that the calling process no longer needs the data contained by the memory block that the call identifies.
Additionally, some applications that have called upon the operating system to allocate them memory will in turn act as allocators in “sub-allocating” that memory. An example of such an application is the Java Virtual Machine (“JVM”). (Java is a trademark or registered trademark of Sun Microsystems, Inc., in the United States and other countries.) Such an application calls upon the operating system to allocate it memory for its private heap, which it sub-allocates to objects created by the virtual-machine-language programs that it executes. The input to the JVM is one or more “class files,” which include virtual-machine programs, i.e., sequences of the virtual machine's instructions. Included in the virtual machine's instruction set are instructions for allocating new objects, and the virtual machine can so operate as to allocate object memory by removing objects from the free-block inventory. The JVM not only executes the class file's explicit instructions but also performs automatic “garbage collection”: it identifies objects that the virtual-machine program will no longer use. The JVM may add such objects' memory space to the free-block inventory after they are thus identified.
Independently of the software-hierarchy level at which an allocator operates, two functions that it must perform are “splitting” and “coalescing.” When a program frees a memory block of a relatively large size, the allocator may initially place it in its free-block inventory as a single block. If a program thereafter requests allocation of a smaller block and no block of the requested size is available, the allocator may split that block into smaller blocks. Conversely, the allocator may have several relatively small contiguous blocks in its inventory, and it may coalesce those blocks into a single composite block. (Workers in this field treat coalesce as a transitive verb.).
Now, many programs have certain phases of operation in which coalescing is significantly less expensive than it is at other times. In the case of a program that periodically performs mark-sweep garbage collection, for instance, memory blocks that are contiguous are identified most readily during the phase in which the program sweeps, i.e., identifies no-longer-needed memory space. It is valuable in some cases to perform coalescing in connection with the sweep operation rather than wait until the need to allocate space for a large object actually arises. Such preemptive coalescing is therefore practiced widely.
But preemptive coalescing can also be counterproductive. If a lot of contiguous blocks are identified and coalesced, the number of smaller blocks may later prove to be inadequate, and blocks resulting from coalescing may simply have to be split again. So some coalescing can prove to be unnecessary and detract from program performance.
To reduce such unnecessary coalescing and splitting, it has been proposed that the allocator use an adaptive policy, one that limits the volume of uncoalesced blocks and adapts the supplies of various-sized blocks to the program's recent usage pattern. Specifically, it has been proposed that memory blocks of selected sizes be put on “quick lists,” whose blocks are not subject to coalescing, but that the quick lists be flushed periodically into the general free-block population, where coalescing is permitted.